1. Field of the Invention
The present invention relates to an architecture for a configurable logic block (CLB) of a field programmable gate array (FPGA). More specifically, the present invention relates to a CLB having circuitry which facilitates both multiplication and general purpose multiplexing.
2. Related Art
FIG. 1 is a representation of the binary multiplication of a 4-bit multiplier number X with a 4-bit multiplicand word Y. Multiplier number X includes bits X3, X2, X1 and X0 (X3 being the most significant bit and X0 being the least significant bit). Similarly, multiplicand word Y includes bits Y3, Y2, Y1 and Y0 (Y3 being the most significant bit and Y0 being the least significant bit). Each bit of multiplier number X is multiplied by each bit of multiplicand word Y as illustrated, thereby creating four partial products 1-4. The first partial product 1 includes each bit of multiplier number X multiplied by Y0. The second partial product 2 includes each bit of multiplier number X multiplied by Y1. Before addition of the partial products, the second partial product 2 is shifted left one place with respect to the first partial product 1, thereby providing the appropriate weight to these partial products. Note that in binary arithmetic, the shifting of the second partial product 2 to the left by one place relative to the first partial product 1 is equivalent to multiplying the second partial product 2 by two. This might also be interpreted as the first partial product 1 having been shifted right one place relative to the second partial product 2, and consequently, divided by two. The third and fourth partial products 3 and 4 are created and weighted in a similar manner. The aligned columns of partial products 1-4 are added to create sum bits S7-S0. Sum bits S7-S0 represent the product P of multiplier number X and multiplicand number Y.
Various conventional multiplier circuits are described below. These multiplier circuits are often implemented in field programmable gate arrays (FPGAs). FPGAs typically include an array of configurable logic blocks (CLBs) which are configured to form a desired circuit. It is desirable to minimize the number of CLBs required to implement a multiplier circuit in an FPGA. It is also desirable to minimize the delay path of the multiplier circuit implemented in the FPGA.
FIG. 2 is a circuit diagram of a conventional 4.times.4 bit multiplier circuit 200 for implementing the multiplication operation illustrated in FIG. 1. Multiplier circuit 200 includes AND gates 201-204, divide-by-two circuits 211-213 and adder circuits 221-223. Each of AND gates 201-204 has a first input terminal which is coupled to receive all of the bits X3-X0 of multiplier number X. The second input terminals of AND gates 201, 202, 203 and 204 are coupled to receive multiplicand bits Y0, Y1, Y2 and Y3, respectively.
The multiplication of two binary bits results in a logic "1" value only if both of the input bits have logic "1" values. A logic "0" value results if either or both of the input bits has a logic "0" value. This is functionally identical to the operation of an AND gate, which can therefore be used to perform the multiplication. As a result, AND gates 201, 202, 203 and 204 provide partial products 1, 2, 3 and 4, respectively.
Adder circuits 221, 222 and 223 sequentially add partial products 1-4, beginning with the least significant partial products. Divide-by-two circuits 211-213 provide the appropriate weighting to partial products 1-4. The AND gate-adder combination (e.g., AND gate 203 and adder 222) is sometimes referred to as a gated adder.
Multiplier circuit 200 disadvantageously requires the use of N gated adder circuits to be cascaded, where N is equal to the number of bits in the multiplicand word Y minus one. As the number of Y bits increases, the delay in creating product P increases linearly.
FIG. 3 is a circuit diagram of another conventional 4.times.4 bit multiplier circuit 300. Multiplier circuit 300 includes AND gate 301, divide-by-two circuits 311-313, adder circuits 321-323 and multiplexers 331-333. AND gate 301 receives multiplier bits X3-X0 on a first input terminal and multiplicand bit Y0 on a second input terminal. As a result, AND gate 301 provides the first partial product 1 to divide-by-two circuit 311.
The weighted first partial product 1 is provided to the "0" input terminal of multiplexer 331 and to an input terminal of adder 321. The other input terminal of gated adder 321 is coupled to receive bits X3-X0 of multiplier number X. The output terminal of adder 321 is provided to the "1" input terminal of multiplexer 331. The control terminal of multiplexer 331 is coupled to receive multiplicand bit Y1.
If multiplicand bit Yl has a logic "0" value, multiplexer 331 simply passes the weighted first partial product 1. This result is appropriate because the second partial product 2 will consist of zero values if multiplicand bit Y1 has a logic "0" value.
If multiplicand bit Y1 has a logic "1" value, multiplexer 331 passes the output signals provided by adder 321. These output signals represent the sum of the first partial product 1 and the second partial product 2 when multiplicand bit Y1 has a logic "1" value. Again, this result matches that of the first gated adder in FIG. 2. Thus, the combination of adder 321 and multiplexer 331 is another form of gated adder.
Similar operations are performed by the remaining elements of multiplier circuit 300 to create product P.
Multiplier circuit 300 is typically implemented in an FPGA in a more efficient manner than multiplier circuit 200. This is because both adder 321 and multiplexer 331 of multiplier circuit 300 can typically be implemented in a single CLB, while AND gates 201 and 202 of multiplier circuit 200 cannot be implemented in the same CLB as adder 221. Thus, more CLBs are required to implement multiplier circuit 200 than multiplier circuit 300. However, multiplier circuit 300 still requires N sequential gated adder circuits 321-323, where N is equal to the number of bits in multiplicand word Y minus one.
FIG. 4 is a circuit diagram of yet another conventional multiplier circuit 400, which includes AND gates 401-404, multiply-by-two circuits 411-412, multiply-by-four circuit 413 and adder circuits 421-423. AND gates 401, 402, 403 and 404 are connected to provide partial products 1, 2, 3 and 4, respectively. Adder circuit 421 adds the first partial product 1 and the second partial product 2 (as weighted by multiply-by-two circuit 411). Adder circuit 422 adds the third partial product 3 and the fourth partial product 4 (as weighted by multiply-by-two circuit 412). Adder circuit 423 adds the output of adder circuit 422 to the output of adder circuit 421 (as weighted by multiply-by-four circuit 413) to provide product P.
Adder circuits 421 and 422 operate in parallel, rather than in series, thereby reducing the total delay of multiplier circuit 400. However, it is relatively inefficient to implement multiplier circuit 400 in an FPGA, since the AND gates 401 and 402 cannot be implemented in the same CLB as adder circuit 421. Multiplier circuit 400 therefore requires a relatively large number of CLBs to implement.
FIG. 5 is a circuit diagram of yet another conventional multiplier circuit 500. Multiplier circuit 500 is similar to multiplier circuit 400 (FIG. 4). Thus, similar elements in FIGS. 4 and 5 are labeled with similar reference numbers. Multiplier circuit 500 replaces the AND gate 401 and adder circuit 421 of multiplier circuit 400 with adder circuit 501 and multiplexer 511. Similarly, multiplier circuit 500 replaces AND gate 403 and adder circuit 422 of multiplier circuit 400 with adder circuit 502 and multiplexer 512. Adder circuits 501-502 and multiplexers 511-512 are connected in a manner similar to that previously described in connection with multiplier 300 (FIG. 3). The resulting multiplier circuit 500 provides the same product P, while eliminating the AND gates 401 and 403 of multiplier circuit 400 (FIG. 4). However, multiplier circuit 500 is still somewhat inefficient to implement in an FPGA, since AND gate 402 cannot be implemented in the same CLBs as adder circuit 501 and multiplexer 511, and since AND gate 404 cannot be implemented in the same CLBs as adder circuit 502 and multiplexer 512. Multiplier circuit 500 therefore requires a relatively large number of CLBs to implement.
FIG. 6 is a circuit diagram illustrating the implementation of adder circuit 421 (FIG. 4) in an FPGA. Adder circuit 421 is implemented by three CLBs 601-603 of the FPGA. Configurable logic blocks 601-603 include F function generators 611-613, G function generators 621-623, F carry logic circuits 631-633 and G carry logic circuits 641-643. Each configurable logic block includes an F function generator, a G function generator, an F carry logic circuit and a G carry logic circuit as illustrated. The first and second partial products 1 and 2 (i.e., X0Y0, X1Y0, X2Y0, X3Y0, and X0Y1, X1Y1, X2Y1, X3Y1) are created by AND gates (e.g., AND gates 403 and 404 of FIG. 4) in CLBs which are external to CLBs 601-603. The first and second partial products 1 and 2 are applied to function generators 611-613 and 621-622 and carry logic circuits 631-633 and 641-642 as illustrated. The illustrated routing of the partial products 1 and 2, along with the "0" values provided to function generators 611 and 613 and carry logic circuits 631 and 633, provide the appropriate weighting to the first and second partial products. In an optimized implementation, F carry logic circuit 631 is not used because its output is always 0, and function generator 611 is not used because input term X.sub.0 Y.sub.0 is the final product SPP.sub.0.
The logic within each function generator/carry logic circuit pair is configured to generate a sum signal and carry signal in response to the three received input signals. For example, F function generator 612 generates a sum signal SPP.sub.2 and F carry logic circuit 632 generates a carry signal C.sub.3 in response to the three input signals X1Y1, X2Y0 and C.sub.2.
Function generators 611-613 and 621-623 provide output signals SPP.sub.0, SPP.sub.1, SPP.sub.2, SPP.sub.3, SPP.sub.4 and SPP.sub.5. These output signals represent the sum of the first and second partial products.
As previously described, the first and second partial products 1 and 2 must be generated by CLBs which are external to CLBs 601-603. As a result, a relatively large number of CLBs are required to implement the gated adder circuit comprising adder 421 and AND gates 401-402 of FIG. 4. This inefficient use of FPGA resources exists for every gated adder circuit of the multiplier circuit. As a result, multiplier circuits cannot be implemented efficiently in conventional CLBs of an FPGA.
Note that each of the F and G function generators 611-613 and 621-623 is typically capable of implementing a multiplexer as well as an adder circuit. For example, F function generator 611 is typically capable of implementing adder circuit 501 and multiplexer 511 of multiplier circuit 500 (FIG. 5). However, AND gates 411, 412 must still be implemented in separate CLBs.
It would therefore be desirable to have an FPGA with CLBs which are capable of efficiently performing multiplication operations. It would also be desirable if such CLBs were capable of efficiently performing other operations, such as multiplexing, when not performing multiplication operations.